package org.regotto.basics.string;

/**
 *
 */
public class Kmp {

    public static void main(String[] args) {

        char[] s = " fabc".toCharArray();
        char[] q = " abc".toCharArray();
        kmp(q, s);


    }

    public static void kmp(char[] q, char[] s) {
        int n = q.length - 1, m = s.length - 1;
        int[] ne = new int[1000];
        // 与自身比较求 ne 数组
        for (int i = 2, j = 0; i <= n; i++) {
            while (j > 0 && q[i] != q[j + 1]) j = ne[j];
            if (q[i] == q[j + 1]) j++;
            ne[i] = j;
        }

        for (int i = 1, j = 0; i <= m; i++) {
            while (j > 0 && s[i] != q[j + 1]) j = ne[j];
            if (s[i] == q[j + 1]) j++;
            if (j == n) {
                System.out.println(i - n);
                j = ne[j];
            }
        }
    }

}